home *** CD-ROM | disk | FTP | other *** search
/ Practical Algorithms for Image Analysis / Practical Algorithms for Image Analysis.iso / CH_5.7 / XSGLL / LLPAR1.C next >
C/C++ Source or Header  |  1999-09-11  |  6KB  |  206 lines
  1. /* 
  2.  * llpar1.c
  3.  * 
  4.  * Practical Algorithms for Image Analysis
  5.  * 
  6.  * Copyright (c) 1997, 1998, 1999 MLMSoftwareGroup, LLC
  7.  */
  8.  
  9.  
  10. /* PARALLELPAR: function takes start and end points of two parallel
  11.  *            lines and returns distance between lines and overlap
  12.  *              of lines
  13.  *                      usage: overlapFlag = 
  14.  *                                      parallelpar (ptO1, ptF1, ptO2, ptF2,
  15.  *                                              &dist, &overlap12)
  16.  *              OverlapFlag is 0 for  no overlap, -1 for perpendicular
  17.  *              lines (which is also no overlap), and 1 for overlap.
  18.  *
  19.  * HISTORY
  20.  * 4-Sept-85  Larry O'Gorman (log) at Bell Labs
  21.  *      This is the umpteenth time the parameter calculation has
  22.  *      been changed, and I'm getting a little tired of doing so.
  23.  *
  24.  * 26-Apr-85  Larry O'Gorman (log) at Bell Labs
  25.  *      Created.
  26.  */
  27. #include <math.h>
  28. #include <stdlib.h>
  29. #include "lldef.h"
  30. #include "sal.h"
  31.  
  32.  
  33. #define OVERLAP 1               /* overlap exists */
  34. #define NOOVERLAP 0             /* no overlap exists */
  35. #define PERPENDICULAR -1        /* no nothing: lines are perpend. */
  36.  
  37.  
  38. int
  39. parallelpar (ptO1, ptF1, ptO2, ptF2, dist, overlap)
  40.      struct point ptO1,         /* initial and final pts of line 1 */
  41.        ptF1, ptO2,              /* initial and final pts of line 2 */
  42.        ptF2;
  43.  
  44.      double *dist,              /* perpendic. dist. between lines */
  45.       *overlap;                 /* overlap between line segments */
  46.  
  47. {
  48.   register double deltaX1,      /* run and rise of line 1 slope */
  49.     deltaY1, deltaX2,           /* run and rise of line 2 slope */
  50.     deltaY2;
  51.  
  52.   struct {                      /* points on line 2 */
  53.     double x, y;
  54.   } pnts[4], midpt[2];
  55.  
  56.   double xO1,                   /* initial (O) and final (F)  */
  57.     yO1,                        /*  points of lines 1 and 2 */
  58.     xF1, yF1, xO2, yO2, xF2, yF2, xA2,  /* intersection pts of perp. on line 2 */
  59.     yA2, xB2, yB2, xM2,         /* middle point of second line */
  60.     yM2, max,                   /* max/min of 4 points on line 2 */
  61.     min, numer,                 /* numerator and denominator */
  62.     denom,                      /*   of distance calculation */
  63.     overlap2,                   /* absolute overlap on line 2 */
  64.     length2,                    /* lenght of line 2 */
  65.     temp;
  66.  
  67.   register long maxI,           /* for ordering points */
  68.     minI, i, j;
  69.  
  70.   int defined;                  /* 1 = overlap; 0 = none */
  71.  
  72. /* initialize */
  73.  
  74.   xO1 = (double) ptO1.x;
  75.   yO1 = (double) ptO1.y;
  76.   xF1 = (double) ptF1.x;
  77.   yF1 = (double) ptF1.y;
  78.   xO2 = (double) ptO2.x;
  79.   yO2 = (double) ptO2.y;
  80.   xF2 = (double) ptF2.x;
  81.   yF2 = (double) ptF2.y;
  82.  
  83.   deltaX1 = xF1 - xO1;
  84.   deltaY1 = yF1 - yO1;
  85.   deltaX2 = xF2 - xO2;
  86.   deltaY2 = yF2 - yO2;
  87.  
  88. /* intersection of perpendiculars from ends of line 1 to line 2 */
  89.  
  90.   temp = (deltaY2 * deltaY1 + deltaX1 * deltaX2);
  91.   if (temp == 0.0)
  92.     return (PERPENDICULAR);
  93.  
  94.   if (deltaX2 != 0.0) {
  95.     xA2 = (1.0 / temp)
  96.       * (xO1 * deltaX2 * deltaX1 + xO2 * deltaY2 * deltaY1
  97.          + deltaX2 * deltaY1 * (yO1 - yO2));
  98.     yA2 = (deltaY2 / deltaX2) * (xA2 - xO2) + yO2;
  99.     xB2 = (1.0 / temp)
  100.       * (xF1 * deltaX2 * deltaX1 + xO2 * deltaY2 * deltaY1
  101.          + deltaX2 * deltaY1 * (yF1 - yO2));
  102.     yB2 = (deltaY2 / deltaX2) * (xB2 - xO2) + yO2;
  103.   }
  104.   else {
  105.     yA2 = (1.0 / temp)
  106.       * (yO1 * deltaY2 * deltaY1 + yO2 * deltaX2 * deltaX1
  107.          + deltaY2 * deltaX1 * (xO1 - xO2));
  108.     xA2 = (deltaX2 / deltaY2) * (yA2 - yO2) + xO2;
  109.     yB2 = (1.0 / temp)
  110.       * (yF1 * deltaY2 * deltaY1 + yO2 * deltaX2 * deltaX1
  111.          + deltaY2 * deltaX1 * (xF1 - xO2));
  112.     xB2 = (deltaX2 / deltaY2) * (yB2 - yO2) + xO2;
  113.   }
  114.  
  115. /* test if intersection points fall outside of line segment 2 */
  116. /* if it does, set defined flag to indicate no overlap, BUT continue
  117.  * with calculations to find direction of line 1 to 2 */
  118.  
  119.   defined = OVERLAP;
  120.   if (deltaX2 != 0.0) {
  121.     if (xA2 >= xO2 && xA2 >= xF2 && xB2 >= xO2 && xB2 >= xF2)
  122.       defined = NOOVERLAP;
  123.     else if (xA2 <= xO2 && xA2 <= xF2 && xB2 <= xO2 && xB2 <= xF2)
  124.       defined = NOOVERLAP;
  125.   }
  126.   else {
  127.     if (yA2 >= yO2 && yA2 >= yF2 && yB2 >= yO2 && yB2 >= yF2)
  128.       defined = NOOVERLAP;
  129.     else if (yA2 <= yO2 && yA2 <= yF2 && yB2 <= yO2 && yB2 <= yF2)
  130.       defined = NOOVERLAP;
  131.   }
  132.  
  133. /* find the middle 2 pnts of overlap (or of no overlap, if none) on line 2 */
  134.  
  135.   pnts[0].x = xO2;
  136.   pnts[0].y = yO2;
  137.   pnts[1].x = xF2;
  138.   pnts[1].y = yF2;
  139.   pnts[2].x = xA2;
  140.   pnts[2].y = yA2;
  141.   pnts[3].x = xB2;
  142.   pnts[3].y = yB2;
  143.  
  144.   if (deltaX2 == 0.0) {
  145.     max = min = pnts[0].y;
  146.     maxI = minI = 0;
  147.     for (i = 1; i < 4; i++) {
  148.       if (pnts[i].y > max) {
  149.         maxI = i;
  150.         max = pnts[i].y;
  151.       }
  152.       else if (pnts[i].y < min) {
  153.         minI = i;
  154.         min = pnts[i].y;
  155.       }
  156.     }
  157.   }
  158.   else {
  159.     max = min = pnts[0].x;
  160.     maxI = minI = 0;
  161.     for (i = 1; i < 4; i++) {
  162.       if (pnts[i].x > max) {
  163.         maxI = i;
  164.         max = pnts[i].x;
  165.       }
  166.       else if (pnts[i].x < min) {
  167.         minI = i;
  168.         min = pnts[i].x;
  169.       }
  170.     }
  171.   }
  172.   for (i = 0, j = 0; i < 4; i++) {
  173.     if (i != minI && i != maxI) {
  174.       midpt[j].x = pnts[i].x;
  175.       midpt[j].y = pnts[i].y;
  176.       j++;
  177.     }
  178.   }
  179.  
  180. /* find dist from line 1 to midpt. of overlap segment on line 2 */
  181.  
  182.   xM2 = (midpt[0].x + midpt[1].x) / 2.0;
  183.   yM2 = (midpt[0].y + midpt[1].y) / 2.0;
  184.  
  185.   if (deltaX1 == 0.0)
  186.     *dist = xM2 - xO1;
  187.   else if (deltaY1 == 0.0)
  188.     *dist = yM2 - yO1;
  189.   else {
  190.     numer = (xM2 - xO1) - (yM2 - yO1) * deltaX1 / deltaY1;
  191.     denom = sqrt ((deltaX1 * deltaX1) / (deltaY1 * deltaY1) + 1.0);
  192.     *dist = numer / denom;
  193.   }
  194.  
  195. /*  calculate overlap */
  196.  
  197.   overlap2 = (midpt[0].x - midpt[1].x) * (midpt[0].x - midpt[1].x)
  198.     + (midpt[0].y - midpt[1].y) * (midpt[0].y - midpt[1].y);
  199.   length2 = (xO2 - xF2) * (xO2 - xF2) + (yO2 - yF2) * (yO2 - yF2);
  200.  
  201.   *overlap = sqrt ((overlap2 / length2)) * 100.0;
  202.  
  203.   return (defined);
  204.  
  205. }
  206.